package com.xxy.recursion;

/**
 * @author xxy
 * @create 2020 11 19 12:48
 * 经典八皇后问题：
 * 1.第一个皇后先放第一行第一列
 * 2.第二个皇后放在第二行第一列，然后判断是否OK，如果不OK，继续放在第二列，第三列，依次把所有列都放完，找到一个合适
 * 3.继续第三个皇后，还是第一列，第二列，。。。直到第8个皇后也能放在不冲突的位置，算是找到了一个正确解
 * 4.当得到一个正确解后，在栈回退到上一个栈时，就开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到
 * 5，然后回头继续第一个皇后，放在第二列，后面循环执行1,2,3步骤。
 * 说明：理论上应该创建一个二维数组来表示棋盘，但是实际不需要
 * 一个一维数组解决问题；
 * arr[8] = {0,4,7,5,2,6,1,3}对应下标，表示第几行，即第几个皇后，arr[i]=val ,val+1,表示第i+1个皇后，放在i+1行的
 * 第val+1列。
 */
public class Queen8 {
    //max表示有多少个皇后
    int max =8;
    int [] array =new int[max];
    static int  count=0;//解放的总数
    //查看当我们放第n个皇后后，就去检测该皇后和前面已经摆放的皇后冲突
    public static void main(String[] args) {
        Queen8 queen8 = new Queen8();
        queen8.check(0);
        System.out.println(count);
    }

       private void check(int n){
           if(n==max){
               print();
               return;//n 等于8，其实8个皇后就都已经放下来
           }
           //放入皇后后，判断是否冲突
           for(int i=0;i<max;i++){
               array[n] =i;
               //判断当放置第n个皇后后到i列时，是否冲突
               if(judgement(n)){//不冲突
                   check(n+1);//放n+1个皇后
               }
               //如果冲突，就继续执行array[n]=i，即将第n个皇后放在本行的后一个位置
           }

       }
       public void print(){
           count++;
           for(int i=0;i<array.length;i++){
               System.out.print(array[i]+" ");
           }
           System.out.println();
       }
    /**
     *检测是否冲突
     * @param第n个皇后
     * @return
     * 1.array[i]==array[n],判断是否是同一列
     * 2.Math.abs(n-i)==Math.abs(array[n]-array[i]，表示判断第n个皇后是否和第i个皇后在同一个斜线上。
     */
    private boolean judgement(int n){
        for(int i=0;i<n;i++){
            if(array[i]==array[n]||Math.abs(n-i)==Math.abs(array[n]-array[i])){
                return false;
            }
        }
        return true;
    }
}
